# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedListToBST(self, head):
        len = 0
        p = head
        while p:
            len += 1
            p = p.next

        cur = head   
    
        def inorderbuild(left, right):
            if left > right:
                return None
            
            mid = (left+right) // 2

            nonlocal cur
            leftTree = inorderbuild(left, mid-1)
            root = TreeNode(cur.val)
            # 如何理解 cur = cur.next
            cur = cur.next
            rightTree = inorderbuild(mid+1, right)
            root.left = leftTree
            root.right = rightTree
            return root
        
        tree = inorderbuild(0, len-1)
        return tree

if __name__ == '__main__':
    s = Solution()
    l = ListNode(-10, 
            ListNode(-3, 
                ListNode(0, 
                    ListNode(5, 
                        ListNode(9)))))

    tree = s.sortedListToBST(l)
